package io.adrainty.algorithm.mars;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 最大矩形面积问题
 * @link <a href="https://www.marscode.cn/practice/364l85wv6oo6lq?problem_id=7414004855077617708">...</a>
 * @author adrainty
 * @version v1.0.0
 * @since 2024/11/25 上午9:10
 */
public class Solution016 {

    private Solution016() {}

    /**
     * 矩形的最大面积 R(k)= k×min(h[i],h[i+1],...,h[i+k−1])
     * @param n array.length
     * @param array 数组
     * @return 对于任意k, R(k)的最大值
     */
    public static int solution(int n, int[] array) {
        // Edit your code here
        // 初始化最大值为只选一个值时数组的第一个元素
        int ans = array[0];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // 维护单调栈，确保栈中的元素是按照高度从小到大排序的
            while (!deque.isEmpty() && array[deque.peekLast()] > array[i]) {
                int height = array[deque.pollLast()];
                int width = deque.isEmpty() ? i : i - deque.peekLast() - 1;
                ans = Math.max(ans, height * width);
            }
            deque.offerLast(i);
        }

        // 处理剩余在栈中的元素
        while (!deque.isEmpty()) {
            int height = array[deque.pollLast()];
            int width = deque.isEmpty() ? n : n - deque.peekLast() - 1;
            ans = Math.max(ans, height * width);
        }

        return ans;
    }

}
